package de.h_da.fbi.cg.pointcloud.util;

import java.util.ArrayList;

import de.h_da.fbi.cg.pointcloud.adt.Edge;
import de.h_da.fbi.cg.pointcloud.adt.Graph;
import de.h_da.fbi.cg.pointcloud.adt.Vertex;
import de.h_da.fbi.cg.pointcloud.spatial.EuclideanDistance;
import de.h_da.fbi.cg.pointcloud.spatial.KDTree;
import de.h_da.fbi.cg.pointcloud.spatial.NearestNeighborSearch;
import de.h_da.fbi.cg.pointcloud.spatial.NearestNeighborSearch.Entry;

/**
 * @author Nicolas Gramlich
 * @since 20:25:25 - 12.11.2010
 */
public class GraphUtil {
	// ===========================================================
	// Constants
	// ===========================================================

	// ===========================================================
	// Fields
	// ===========================================================

	// ===========================================================
	// Constructors
	// ===========================================================

	// ===========================================================
	// Getter & Setter
	// ===========================================================

	// ===========================================================
	// Methods for/from SuperClass/Interfaces
	// ===========================================================

	// ===========================================================
	// Methods
	// ===========================================================

	public static ArrayList<Graph> createComponentsWithNearestNeighborEdges(final ArrayList<Vertex> pVertices, final int pNearestNeighborCount) {
		final KDTree<Float, Vertex, Void> kdTree = new KDTree<Float, Vertex, Void>(3);

		final int vertexCount = pVertices.size();
		for(int i = 0; i < vertexCount; i++) {
			final Vertex vertex = pVertices.get(i);
			kdTree.put(vertex, null);
		}

		kdTree.balance();

		final NearestNeighborSearch<Float, Vertex, Void> nnSearch = new NearestNeighborSearch<Float, Vertex, Void>(new EuclideanDistance<Float, Vertex>());

		final ArrayList<Graph> components = new ArrayList<Graph>(vertexCount);

		for(int i = 0; i < vertexCount; i++) {
			final Graph component = new Graph();
			final Vertex vertex = pVertices.get(i);
			component.addVertex(vertex);

			final Entry<Float, Vertex, Void>[] neighbors =  nnSearch.get(kdTree, vertex, pNearestNeighborCount, true);

			for(final Entry<Float, Vertex, Void> neighborEntry : neighbors) {
				final Vertex neighbor = neighborEntry.getKey();

				final Edge edge = new Edge(vertex, neighbor);

				component.addEdge(edge);
			}
			components.add(component);
		}

		return components;
	}

	// ===========================================================
	// Inner and Anonymous Classes
	// ===========================================================
}
